package leetcode_top;
import java.util.*;

import tree.*;

public class Ex103 {
    class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            if (root == null) return new LinkedList<>();
            Deque<TreeNode> deque = new LinkedList<>();
            deque.offer(root);
            boolean flag = true; //true表示正向打印
            int n;
            TreeNode cur;
            List<List<Integer>> res = new ArrayList<>();
            while (!deque.isEmpty()) {
                n = deque.size();
                List<Integer> list = new ArrayList<>();
                for (int i = 0; i < n; i++) {
                    if (flag) {
                        cur = deque.pollFirst();
                        list.add(cur.val);
                        if (cur.left != null) {
                            deque.offerLast(cur.left);
                        }
                        if (cur.right != null) {
                            deque.offerLast(cur.right);
                        }
                    } else {
                        cur = deque.pollLast();
                        list.add(cur.val);
                        if (cur.right != null) {
                            deque.offerFirst(cur.right);
                        }
                        if (cur.left != null) {
                            deque.offerFirst(cur.left);
                        }
                    }
                }
                res.add(list);
                flag = !flag;
            }
            return res;
        }
    }
}
